COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00003 00003	\section{Propositional terms.}
C00017 00004	\section{The function {\it eval}.}
C00035 00005	        Since any computation can be described as evaluating an expression
C00039 00006	        When you talk to \lisp\ you do not explicitly tell the interpreter
C00041 00007		Lisp is a programming language for computing with the
C00046 ENDMK
C⊗;

        The value of a propositional term can be determined using the truth 
table given in \tabref{propop}.  

\begin{table}
\label{propop}

$$\vbox{\halign{$#$\hfil&\qquad$#$\hfil&\qquad$#$\hfil\cr
      \qT \qand \qT  = \qT & \qT \qor \qT  = \qT\cr
      \qT \qand \qNIL = \qNIL  & \qT \qor \qNIL = \qT &  \qnot \qT  = \qNIL\cr
     \qNIL \qand \qT  = \qNIL &     \qNIL \qor \qT  = \qT \qnot \qNIL = \qT\cr
     \qNIL \qand \qNIL = \qNIL &     \qNIL \qor \qNIL = \qNIL  \cr
}}$$

\caption{Truth table for propositional terms.}
\end{table}

\section{Propositional terms.}
\label{andor}

        As mentioned in the previous section,
propositional terms are a terms whose value represents a truth value.
The simplest propositional terms are the constants \qT\ and \qNIL.  
If \qp is a predicate of n-arguments then $\qp[x_1,\ \ldots\ x_n]$ is a 
propositional term.  Additional propositional terms can be formed by combining 
terms already formed using the logical operations of
conjunction(\qand), disjunction(\qor) and negation(\qnot).
Both \qand\ and \qor\ are associative, so we can write expressions
like $p_1 \qand p_2 \qand p_3$ without worrying about the grouping.  

        The evaluation of propositional terms is defined using conditional 
terms as follows:
%
$$\vbox{\ialign{\hfil $#$&$\>=#$\hfil\cr
  p \qand q & \qif p \qthen q \qelse \qNIL\cr
  p \qor q & \qif p \qthen p \qelse q\cr
  \qnot p & \qif p \qthen \qNIL \qelse \qT\cr
}}$$
%
The internal forms of these definitions are
%
$$\vbox{\halign{\hfil \sx # &$=$\ \sx #\hfil\cr
     (AND P Q) & (COND (P Q) (T NIL))\cr
      (OR P Q) & (COND (P P) (T Q))  \cr
       (NOT P) & (COND (P NIL) (T T))\cr
}}$$
%
Note that if $p$ is false then $p \qand q = \qNIL$ independent of the value of
$q$, and likewise if $p$ is true, then $p \qor q = \qT$ is independent of
$q$.  If $p$ has been evaluated and found to be false, then $q$ does
not have to be evaluated at all to find the value of $p \qand q$, and, in
fact, \LISP does not evaluate $q$ in this case.  Similarly, $q$ is not
evaluated in evaluating $p \qor q$ if $p$ is true. This procedure is in
accordance with the above conditional expression descriptions of
these operators.  The importance of this convention, which contrasts
with that of ALGOL 60, will be apparent later when we discuss
recursive definitions of functions and predicates.  

        Propositional expressions can be combined with functions and conditional
expressions to get terms like
%
$$\qif [\qn u \qor \qn \qd u] \qthen u \qelse \qa u \qcons {\it alt} \qdd u$$
%
whose internal form is
%
$$|(IF (OR (NULL U) (NULL (CDR U))) U  (CONS (CAR U) (ALT (CDDR U))))|.$$

        We conclude this section with two remarks.  First, the only 
S-expressions that we have said represent truthvalues are \qT\ and \qNIL.
However, \LISP implementations regard any non-\qNIL\ S-expression as
representing \qtrue.  \LISPs doesn't distinguish between between 
propositional terms and more general terms.  Thus any term can appear in
the $p$ part of a conditional term.  Second, 
\LISP implementations allow \qand\ and \qor\ to have arbitrary numbers
of arguments.

\section{Propositional terms.}
\label{andor}

        As mentioned in the previous section,
propositional terms are a terms whose value represents a truth value.
The simplest propositional terms are the constants \qT\ and \qNIL.  
If \qp is a predicate of n-arguments then $\qp[x_1,\ \ldots\ x_n]$ is a 
propositional term.  Additional propositional terms can be formed by combining 
terms already formed using the logical operations of
conjunction(\qand), disjunction(\qor) and negation(\qnot).
Both \qand\ and \qor\ are associative, so we can write expressions
like $p_1 \qand p_2 \qand p_3$ without worrying about the grouping.  

        The evaluation of propositional terms is defined using conditional 
terms as follows:
%
$$\vbox{\ialign{\hfil $#$&$\>=#$\hfil\cr
  p \qand q & \qif p \qthen q \qelse \qNIL\cr
  p \qor q & \qif p \qthen p \qelse q\cr
  \qnot p & \qif p \qthen \qNIL \qelse \qT\cr
}}$$
%
The internal forms of these definitions are
%
$$\vbox{\halign{\hfil \sx # &$=$\ \sx #\hfil\cr
     (AND P Q) & (COND (P Q) (T NIL))\cr
      (OR P Q) & (COND (P P) (T Q))  \cr
       (NOT P) & (COND (P NIL) (T T))\cr
}}$$
%
Note that if $p$ is false then $p \qand q = \qNIL$ independent of the value of
$q$, and likewise if $p$ is true, then $p \qor q = \qT$ is independent of
$q$.  If $p$ has been evaluated and found to be false, then $q$ does
not have to be evaluated at all to find the value of $p \qand q$, and, in
fact, \LISP does not evaluate $q$ in this case.  Similarly, $q$ is not
evaluated in evaluating $p \qor q$ if $p$ is true. This procedure is in
accordance with the above conditional expression descriptions of
these operators.  The importance of this convention, which contrasts
with that of ALGOL 60, will be apparent later when we discuss
recursive definitions of functions and predicates.  

        Propositional expressions can be combined with functions and conditional
expressions to get terms like
%
$$\qif [\qn u \qor \qn \qd u] \qthen u \qelse \qa u \qcons {\it alt} \qdd u$$
%
whose internal form is
%
$$|(IF (OR (NULL U) (NULL (CDR U))) U  (CONS (CAR U) (ALT (CDDR U))))|.$$

        We conclude this section with two remarks.  First, the only 
S-expressions that we have said represent truthvalues are \qT\ and \qNIL.
However, \LISP implementations regard any non-\qNIL\ S-expression as
representing \qtrue.  \LISPs doesn't distinguish between between 
propositional terms and more general terms.  Thus any term can appear in
the $p$ part of a conditional term.  Second, 
\LISP implementations allow \qand\ and \qor\ to have arbitrary numbers
of arguments.

\section{The function {\it eval}.}
\label{evaluator}

        \mkop{eval} plays both a theoretical and a practical role in \lisp.
Historically, the list notation for \lisp\ functions and \mkop{eval} were first
devised in order to show how easy it is to define a universal function in \lisp\ -
the idea was to advocate \lisp\ as an alternative to Turing machines for doing
the elementary theory of computability.  This role will be discussed in a later
chapter.   S. R. Russell noted that
\mkop{eval} could serve as an interpreter for \lisp\ and promptly programmed it
in machine language with minor modifications to make it more practical.
An interpreter based on \mkop{eval} has remained a feature of most \lisp\ systems.
Thus when you talking to \lisp\ the system is in a loop that \mkop{read}s what you
type, \mkop{eval}s it and \mkop{print}s the result.   [Of course a real \lisp\ system
does many other things too, such a storage management, error handling, 
etc.]

        \mkop{eval} for \lisp\ expressions is analogous to the
interpreter \mkop{numval} for arithmetic expressions given in \defref{numval}.
The first argument to \mkop{eval} is a \lisp\ expression
in internal notation.  The second argument is an association list that
tells \mkop{eval} what value each variable has, and what function definition
is to be associated with each function name.  Thus the association list is 
a list of pairs where each pair consists either of a variable and the S-expression 
corresponding to its value, or a function name and the S-expression
representing the function expression defining the function.  
(Here a function expression is either a function name, or a lambda expression.)
The result of applying \mkop{eval} is the value of the term represented by the
S-expression in an
environment where the free variables are assigned the values given by
the association list and where the function names occuring free (i.e. not
bound in a label expression) denote functions defined by the associated 
expressions in the association list.

        Since any computation can be described as evaluating an expression
without free variables or function names, the second argument theoretically
plays a role mainly in the recursive definition of \mkop{eval}.  Thus 
we usually start our computations with the second argument \qNIL.

        To illustrate this, suppose we want to apply the function \mkop{alt}
to the list |(A B C D E)|, i.e. we wish to evaluate $\mkop{alt}[|(A B C D E)|]$.
This can be obtained by computing
$$\vbox{\ialign{\hfil$#$&&\sx #\hfil\cr
  \mkop{eval}[&(ALT (QU&OTE (A &B C D E))),\cr
              &((ALT LA&MBDA (X&)\cr
              &        &(COND (&(OR (NULL X) (NULL (CDR X))) X)\cr
              &        &       &(T (CONS (CAR X) (ALT (CDDR X)))))))$]$.\cr
}}$$

        A simplified version of the usual \lisp\ \mkop{eval} is the following:
$$\edefun{eval}{%
}$$
%  ∂(n)⊗⊗eval[e, a] ←⊗
%  ∂(n+4)       ⊗⊗qif qat e qthen [qif numberp e qor e  = qNIL qor e = qT qthen e 
%  qelse qd assoc[e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qat qa e qthen⊗
%  ∂(n+8)               ⊗⊗[qif qa e = $QUOTE qthen qad e⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $COND qthen evcond[qd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $LIST qthen evlist[qd e,a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CAR qthen qa eval[qad e, a]⊗
%  !fcneval&l ∂(n+8)⊗⊗qelse qif qa e = $CDR qthen qd eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CONS qthen eval[qad e, a] . eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $ATOM qthen qat eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $EQ qthen  eval[qad e, a] qeq eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse eval[qd assoc[qa e, a] . qd e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LAMBDA qthen eval[qadda e, prup[qada e, evlist[qd e,a]] * a]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LABEL qthen eval[qadda e . qd e, [qada e . qadda e] . a]⊗, 
%  
%  where the auxiliary functions ⊗evcond and ⊗evlist are defined by
%  
%  !fcnevcond&  ⊗⊗⊗evcond[u, a] ← qif eval[qaa u, a] qthen eval[qada u, a]  qelse evcond[qd u, a]⊗, 
%  
%  !fcnevlist&  ⊗⊗⊗evlist[u, a] ← qif qn u qthen qNIL qelse eval[qa u,a] . evlist[qd u, a]⊗,
%  
%  and the auxiliary function ⊗prup, used for pairing up the elements of two
%  lists of equal length, is defined by
%  
%  !fcnprup&  ⊗⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u,qd v]⊗.
%  Recall that ⊗assoc is defined by
%  
%  !eqnassoc1  ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗

        This simple \mkop{eval} expects that an expression is either a
constant ({\it number}, \qT, \qNIL, or a |QUOTE|d S-expression),
a variable whose value can be found on the association list, 
a conditional expression, a list making
expression, or an application of a function or lambda expression
to a list of arguments.  Thus \mkop{eval} checks to see
which of the above classes the expression to be evaluated falls into
and proceeds accordingly.  If the expression, $e$, is atomic then it is either
a non |QUOTE|d constant or a variable.  If the former then \mkop{eval} just returns
the expression, if the latter it looks up the value on the association list, $a$.  

        If $e$ is non-atomic but $\qa e$ is atomic then $e$ is either
a |QUOTE|d constant, a conditional, a list maker, or an application of a
function to a list of arguments.  In the constant case the expression
being quoted ($\qad e$) is returned.  If $e$ is a conditional then the list
of pairs is processed by the auxiliary evaluator \mkop{evcond}, which 
\mkop{eval}s the ``if'' parts ($\qaa u$) in order until a true one is found then
returns the result of \mkop{eval}ing the corresponding ``then'' part ($\qada u$).
In the list case the list of expressions to be evaluated
is given to \mkop{evlist} which returns a list of the values.
In the function application case there are two 
possibilities.  If the function to be applied
is one of the elementary functions, the indicated operation is performed
on the result of evaluating the arguments.  Otherwise the function must
be defined in $a$, so \mkop{eval} looks up the definition, replaces the function 
name by the function definition in the expression and restarts the evaluation.

        If neither $e$ nor $\qa e$ are atomic then it must be a lambda 
application.  In the lambda case the argument list is given to \mkop{evlist} to
be evaluated, the values are then paired with the list of variables to be
bound by the lambda ($\qada e$) using \mkop{prup} and put on the front of $a$. 
The body of the lambda ($\qadda e$) is then evaluated using this new 
association list. 

        If $e$ is not an expression of the sort expected by \mkop{eval}, then
the result is not defined.   It would not be difficult to add additional
clauses to \mkop{eval} so that it would return reasonable error messages rather
than just being undefined (or dying in some strange way as would be
likely in an actual computer).  It would be necessary to be make the
error messages distinguishable from legitimate values of the expression
so that errors at inner levels of evaluation could be passed up the chain.
This could be done by returning legitimate values as pairs whose first
element is one atom and error messages as pairs prefixed by another.
Terms containing \mkop{eval} would have to distinguish the cases.

       Notice that 
|COND| and |LIST| considered as pseudo-functions behave differently
than ordinary functions in that both can take
an arbitrary number of arguments while functions defined by a lambda
expression have a fixed number of arguments determined by the variable list
occuring in the lambda expression.  Also, the usual manner of evaluation
an application term is \lisp\ is to evaluate all of the arguments then
apply the function.  This will not work for |COND| as the main reason for
a conditional is to be able to select a term to evaluate depending on
some set of conditions and not to evaluate other terms under those conditions.

        The above version of \mkop{eval} does not handle the propositional
constructs \qand, \qor, and \qnot.  The effect of these constructs
can be obtained by appropriate use of the condtional, but simply
defining functions for \qand\ and \qor\ will not work as the evaluation
of a function application requires that all of the arguments of 
of the function be evaluated before it is applied while the specification
of \qand\ and \qor\ require that only as many of the arguments be evaluated
as are required to determine the answer.  
Another problem is that in most implementations 
they are allowed to take an arbitrary number of arguments.   Thus
we need to build them into \mkop{eval} for things to work properly.
We will see later that \lisp\ systems provide alternate solutions to
this problem by providing a variety of modes of function application.
(These are known as |EXPR| and |LEXPR|s.)   Macros are also
used for this purpose and will be explained later.  Arithmetic is
also missing from our \mkop{eval}.  Adding these constructs is essentially
like combining \mkop{eval} with the earlier evaluator \mkop{numval} and adding
any additional primitive operations that are desired.

        We note that \mkop{eval} can evaluate itself if it is given an
association list, $eval-alist$, containing the definition of \mkop{eval}
represented as s-expressions.  Thus
$$\mkop{eval}[|(EVAL '(CAR '(A.B)) NIL)|,eval-alist] = |A|.$$

        When you talk to \lisp\ you do not explicitly tell the interpreter
what association list to use generally.  This is because 
the \lisp\ associates with each atom a list of properties,  among these
are the value, and/or the function definition associated with that
atom.  The \lisp\ interpreter typically
looks up variable values and function definitions on the corresponding 
property lists.  Thus, instead of making up an association list
with the appropriate variables and functions defined, the property
lists must first be primed by doing |SETQ|s for giving variables
initial values and |DEFUN|s for any functions
that need to be defined.  These features will be discussed in
more detail in \chapref{IMPURE}.

\subsubsection*{Exercises}
\begin{list}{\arabic{list}.}{\leftmargin0pt \labelwidth -\parindent}

\item What is the value of 
$$\vbox{\ialign{\hfil$#$&$#$\hfil\cr
  \mkop{eval}[&|(LEFT (QUOTE (A . B)))|,\cr
              &|((LEFT LAMBDA (X) (COND ((ATOM X) X) (T (LEFT (CAR X))))))|]?\cr
}}$$

\item Translate the definition of \mkop{eval} given above into internal notation.

\item  Go to your nearest \lisp\ system, type in your answer to the second exercise
and use it to check your answer to the first exercise.

\end{list}
        Since any computation can be described as evaluating an expression
without free variables or function names, the second argument theoretically
plays a role mainly in the recursive definition of \mkop{eval}.  Thus 
we usually start our computations with the second argument \qNIL.

        To illustrate this, suppose we want to apply the function \mkop{alt}
to the list |(A B C D E)|, i.e. we wish to evaluate $\mkop{alt}[|(A B C D E)|]$.
This can be obtained by computing
$$\vbox{\ialign{\hfil$#$&&\sx #\hfil\cr
  \mkop{eval}[&(ALT (QU&OTE (A &B C D E))),\cr
              &((ALT LA&MBDA (X&)\cr
              &        &(COND (&(OR (NULL X) (NULL (CDR X))) X)\cr
              &        &       &(T (CONS (CAR X) (ALT (CDDR X)))))))$]$.\cr
}}$$

$$\edefun{eval}{%
}$$
%  ∂(n)⊗⊗eval[e, a] ←⊗
%  ∂(n+4)       ⊗⊗qif qat e qthen [qif numberp e qor e  = qNIL qor e = qT qthen e 
%  qelse qd assoc[e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qat qa e qthen⊗
%  ∂(n+8)               ⊗⊗[qif qa e = $QUOTE qthen qad e⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $COND qthen evcond[qd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $LIST qthen evlist[qd e,a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CAR qthen qa eval[qad e, a]⊗
%  !fcneval&l ∂(n+8)⊗⊗qelse qif qa e = $CDR qthen qd eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $CONS qthen eval[qad e, a] . eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $ATOM qthen qat eval[qad e, a]⊗
%  ∂(n+8)               ⊗⊗qelse qif qa e = $EQ qthen  eval[qad e, a] qeq eval[qadd e, a]⊗
%  ∂(n+8)               ⊗⊗qelse eval[qd assoc[qa e, a] . qd e, a]]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LAMBDA qthen eval[qadda e, prup[qada e, evlist[qd e,a]] * a]⊗
%  ∂(n+4)       ⊗⊗qelse qif qaa e = $LABEL qthen eval[qadda e . qd e, [qada e . qadda e] . a]⊗, 
%  
%  where the auxiliary functions ⊗evcond and ⊗evlist are defined by
%  
%  !fcnevcond&  ⊗⊗⊗evcond[u, a] ← qif eval[qaa u, a] qthen eval[qada u, a]  qelse evcond[qd u, a]⊗, 
%  
%  !fcnevlist&  ⊗⊗⊗evlist[u, a] ← qif qn u qthen qNIL qelse eval[qa u,a] . evlist[qd u, a]⊗,
%  
%  and the auxiliary function ⊗prup, used for pairing up the elements of two
%  lists of equal length, is defined by
%  
%  !fcnprup&  ⊗⊗⊗prup[u, v] ← qif qn u qthen qNIL qelse [qa u . qa v] . prup[qd u,qd v]⊗.
%  Recall that ⊗assoc is defined by
%  
%  !eqnassoc1  ⊗⊗⊗assoc[x,a] ← qif qn a qthen qNIL qelse qif qaa a qeq x qthen qa a qelse assoc[x,qd a].⊗
        When you talk to \lisp\ you do not explicitly tell the interpreter
what association list to use generally.  This is because 
the \lisp\ associates with each atom a list of properties,  among these
are the value, and/or the function definition associated with that
atom.  The \lisp\ interpreter typically
looks up variable values and function definitions on the corresponding 
property lists.  Thus, instead of making up an association list
with the appropriate variables and functions defined, the property
lists must first be primed by doing |SETQ|s for giving variables
initial values and |DEFUN|s for any functions
that need to be defined.  These features will be discussed in
more detail in \chapref{IMPURE}.
	Lisp is a programming language for computing with the
symbolic expressions that arise in artificial intelligence and
in computation with mathematical formulas.  The core of the
language is called pure Lisp and we begin with that.  Pure
Lisp is most clearly explained rather abstractly.  The data
of Lisp are called S-expressions.

	Begin with a set {\it A} called the set of atoms.  For our
present purpose it doesn't matter what the atoms are.  We only
need to provide a test for equality of two atoms and a predicate
for telling whether an object is an atom.  In this section we'll
use $=$ for equality, e.g we write $x = y$, and $\qat$ for the
atom test.  Because, we will need parentheses for Lisp S-expressions,
we use square brackets for applying a function to arguments.
Thus we write $\qat[x]$ for the assertion that {\it x} is an
atom.  However, when there is no ambiguity, we reduce the number
of brackets by omitting them for functions of one argument.  Thus
we simply write $\qat x$.

	S-expressions are built up from atoms by the following rule.

	{\it An atom is an S-expression, and an ordered pair of
S-expressions is an S-expression.  All S-expressions are formed
in this way.}

	From this abstract point of view we need say nothing about
how S-expressions are represented in the memory of a computer or
on paper.  We do need names for the basic operations on S-expressions.
The operation that forms pairs is called {\it cons} in Lisp.  Thus if
{\it x} and {\it y} are S-expressions, then $cons[x,y]$ is the
pair whose first and second elements are {\it x} and {\it y} respectively.
It is also written $x\qcons y$ when an infix notation is
more convenient.  The operations for taking the components of a pair
are called {\it car} and {\it cdr}.  We write $car[x]$ and $cdr[x]$
or more briefly $\qa\ x$ and $\qd\ x$.  We have the equations
%
	$$car[cons[x,y]] = x$$
%
and
%
	$$cdr[cons[x,y]] = y$$
%
or in the shorter notation
%
	$$\qa\ [x\qcons y] = x$$
%
and
%
	$$\qd\ [x\qcons y] = y.$$
%
We apologize for all these variant notations, but they exist for
historical reasons, and they are all needed to read this book and
other Lisp literature.

	We need a notation for constant S-expressions.  For the
moment we'll use capital letters for atoms, so that {\sx A},
{\sx B}, etc. denote atoms.  The pairs are formed by surrounding
the paired items by parentheses and separating them with a dot.
Thus {\sx A}, {\sx (A.A)}, {\sx (A.B)} and {\sx ((A.B).(A.(B.C)))}
are all S-expressions.  It is important to distinguish the
operation {\it cons} or $\qcons$ that forms S-expressions from
the dot used in writing S-expressions.  The former is an operation
that can be executed, i.e. a program getting {\it x} and {\it y},
computes $x\qcons y$, whatever $x$ and $y$ may be, while {\sx (A.B)}
just denotes that one S-expression.  We have
%
	$${\sx A}\qcons {\sx B} = {\sx (A.B)},$$
%
but we can't write $(x.y)$.  Notice that $\qcons$ is a raised dot.

	We also postulate that a pair is never an atom, and this is
expressed by the formula
%
	$$¬\qat[x\qcons y].$$